Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep versus plane sweep

We present an extensive experimental study comparing the performance of four algorithms for the following orthogonal segment intersection problem: given a set of horizontal and vertical line segments in the plane, report all intersecting horizontal-vertical pairs. The problem has important applications in VLSI layout and graphics, which are large-scale in nature. The algorithms under evaluation are our implementations of distribution sweep and three variations of plane sweep. Distribution sweep is specifically designed for the situations in which the problem is too large to be solved in internal memory, and theoretically has optimal I/O cost. Plane sweep is a well-known and powerful technique in computational geometry, and is optimal for this particular problem in terms of internal computation. The three variations of plane sweep differ by the sorting methods (external versus internal sorting) used in the preprocessing phase and the dynamic data structures (B-tree versus 2-3-4-tree) used in the sweeping phase. We generate the test data by three programs that use a random number generator while producing some interesting properties that are predicted by our theoretical analysis. The sizes of the test data range from 250 thousand segments to 2.5 million segments. The experiments provide detailed quantitative evaluation of the performance of the four algorithms, and the observed behavior of the algorithms is consistent with their theoretical properties. This is, to the best of our knowledge, the first experimental algorithmic study comparing the practical performance between external-memory algorithms and conventional algorithms with large-scale test data.     

非线性约束优化问题的一个修正 Lagrangian 算法

基于一个含有控制参数的修正Lagrangian函数,该文建立了一个求解非线性约束优化问题的修正Lagrangian算法.在一些适当的条件下,证明了控制参数存在一个阀值,当控制参数小于这一阀值时,由这一算法产生的序列解局部收敛于问题的Kuhn-Tucker点,并且建立了解的误差上界.最后给出一些约束优化问题的数值结果.     

基于RBF网络信道均衡器

在数字通信系统中为了克服信道畸变引起的码间干扰，在接收端必须采用信道均衡技术。在本文中，我们将RBF网络用作均衡器。采用最近邻聚类和直接判决算法来调整隐藏层中心，然后再用LMS算法调整输出层的系数。该算法可以实现在线学习，根据相应的准则增加，删除隐藏层节点。算法事先不必确定隐藏层的节点个数。模拟结果显示，RBF网络均衡器能够正确地将信号从有噪信道中恢复出来，在计算机模拟仿真中其性能与理想贝叶斯均衡器相当。     

一种新型广义RBF神经网络在混沌时间序列预测中的研究

提出了一种新颖的广义径向基函数神经网络模型,其径向基函数(RBF)的形式由生成函数确定.然后,给出了易实现的梯度学习算法,同时为了进一步提高网络的收敛速度和网络性能,又给出了基于卡尔曼滤波的动态学习算法.为了验证网络的学习性能，采用基于卡尔曼滤波算法的新型广义RBF网络预测模型对Mackey-Glass混沌时间序列和Henon映射进行了仿真.结果表明,所提出的新型广义RBF神经网络模型能快速、精确地预测混沌时间序列,是研究复杂非线性动力系统辨识和控制的一种有效方法. 关键词： 广义径向基函数神经网络 卡尔曼滤波 梯度下降学习算法 混沌时间序列 预测     

一种生成对称群S9所有Sylow-p子群的算法

根据对称群的基本性质以及第二同构定理，给出了通过添加生成元到P群来构造对称群的一个Sylow-p子群的定理，添加的生成元保证能够快速得到对称群的一个Sylow—p子群．根据第二西洛定理求出了所有共轭子群，即所有Sylow-p子群．针对求所有共轭子群过程中面临共轭子群出现重复的问题，利用正规化子的性质，找到使得两个Sylow-p子群共轭的元，保证每次求的Sylow-P子群不重复．将此算法应用于S1，实验表明该算法可操作性强，耗费时间少．     

基于概念的教育资源元素材聚类方法研究

针对教育资源元素材种类多、独立性强等特点，研究了概念聚类方法解决领域知识的分类和归并问题，并实现了概念的动态聚类算法和归并算法，分析了该算法的效率和聚类准确性．     

椭圆曲线素阶群上的离散对数求解

该文对解椭圆曲线上离散对数的Pollard ρ算法和并行碰撞搜索算法分别建立了它 们的图论模型和分析了碰撞技巧,比较了两个算法,进而提出了设计迭代函数的准则并 给出一个改进的并行碰撞算法.     

Optimal broadcast domination in polynomial time

Broadcast domination was introduced by Erwin in 2002, and it is a variant of the standard dominating set problem, such that different vertices can be assigned different domination powers. Broadcast domination assigns an integer power f(v)?0 to each vertex v of a given graph, such that every vertex of the graph is within distance f(v) from some vertex v having f(v)?1. The optimal broadcast domination problem seeks to minimize the sum of the powers assigned to the vertices of the graph. Since the presentation of this problem its computational complexity has been open, and the general belief has been that it might be NP-hard. In this paper, we show that optimal broadcast domination is actually in P, and we give a polynomial time algorithm for solving the problem on arbitrary graphs, using a non-standard approach.     

Relaxation time for a dimer covering with height representation

This paper considers the Monte Carlo dynamics of random dimer coverings of the square lattice, which can be mapped to a rough interface model. Two kinds of slow modes are identified, associated respectively with long-wavelength fluctuations of the interface height, and with slow drift (in time) of the system-wide mean height. Within a continuum theory, the longest relaxation time for either kind of mode scales as the system sizeN. For the real, discrete model, an exactlower bound ofO(N) is placed on the relaxation time, using variational eigenfunctions corresponding to the two kinds of continuum modes     

A vector Chebyshev algorithm

We consider polynomials orthogonal relative to a sequence of vectors and derive their recurrence relations within the framework of Clifford algebras. We state sufficient conditions for the existence of a system of such polynomials. The coefficients in the above relations may be computed using a cross-rule which is linked to a vector version of the quotient-difference algorithm, both of which are proved here using designants. An alternative route is to employ a vector variant of the Chebyshev algorithm. This algorithm is established and an implementation presented which does not require general Clifford elements. Finally, we comment on the connection with vector Padé approximants. This revised version was published online in June 2006 with corrections to the Cover Date.